Distance Fields
In computer graphics applications, a three-dimensional (3D) object can be represented using a number of different methods, e.g., methods that use polygonal models, point cloud models, parametric functions, or implicit functions.
One class of methods uses a distance field that specifies a minimum distance d(x) from any location x=(x, y, z) in 3D space to a surface of the object. The distance field d(x) can distinguish the inside, the outside and the surface of the object, e.g., d(x)<0 is outside, d(x)>0 is inside, and d(x)=0 is on the surface of the object.
Furthermore, the distance field can be used to locate surfaces that are offset from the actual surface of the object, i.e., offset from d(x)=0. In general, the surface criterion is defined as d(x)=c, where c is a constant distance offset from the object's surface and may be equal to 0. Alternately, a new offset distance field D(x)=d(x)−c can be used such that the offset surface satisfies the condition that D(x)=0. It is to be understood throughout this description that the offset distance field can he used in place of the actual distance field without loss of generality.
The distance field of an object can be specified by a number of different means. For simple geometric objects, the distance field can be specified analytically. For example, the distance field of a sphere of radius R centered at 3D coordinates (x0, y0, z0) can be written as d(x)=R−sqrt[(x−x0)2+(y−y0)2+(z−z0)2]. In this case, the parameters R and (x0, y0, z0), in combination with the distance function of the sphere, are sufficient to fully specify the distance field and hence the 3D shape of the object. In general, a 3D distance field can be specified by a set of parameters p={p0, p1 . . . pn} and a distance function f(x, y, z, p0, p1 . . . pn).
The distance function f can be a combination of other functions. For example, the object may be a composite object formed by the UNION of two objects, such as a sphere and a cube. In this case a point in 3D space x is inside the surface of the composite object if dsphere(x)>0 OR if dcube(x)>0, where OR is the Boolean OR function. This combination of objects by the Boolean operations, UNION, INTERSECTION, and DIFFERENCE, is well known in the art as constructive solid geometry (CSG).
For some applications of distance fields, such as computer simulation, it may be useful to compute and store in memory, i.e., sample, the distance field at an array of locations in 3D space. Although distance field sampling on a regular 3D grid has the benefit of simplicity, the spatial sampling rate needs to be high enough to capture the highest spatial frequencies present in Additionally, it may be useful to partition the 3D space into regions in which different distance functions and/or parameters are used in different regions. For example, the distance function may be that of a sphere in a region of space that extends from (xa, ya, za) to (xb, yb, zb), while the distance function may be that of the cube in a region of space that extends from (xc, yc, zc) to (xd, yd, zd). Herein, these regions of space are defined as cells with the coordinates of the corners of the cells as vertices.
Space-partitioning may be done by many means. It may be useful to use cells that are rectangular or cubic in shape, but other arbitrary cell shapes can be used without a loss of generality. Additionally, it may be useful to organize the cells into a data structure, such as a tree, to enable locating cells having specific spatial relationships. For example, the cells may be cubic and be arranged in simple cubic grid, or in an octree data structure. Alternately, the cells may be rectangular and arranged in a k-dimensional tree structure.
For some applications of distance fields, such as computer simulation, it may be useful to compute and store in memory, i.e., sample, the distance field at an array of locations in 3D space. Although distance field sampling on a regular 3D grid has the benefit of simplicity, the spatial sampling rate needs to be high enough to capture the highest spatial frequencies present in the surface of the object. However, only in extreme cases do these high frequencies exist everywhere on the surface. More typically, the surface includes smooth portions, which could be sampled at lower rates without loss of detail.
In a 3D adaptively sampled distance field (ADF), the distance field is sampled at a spatial frequency that varies in space in proportion to a local level of detail of the surface of the object. Portions of the surface of the object with a large amount of spatial detail are sampled at a higher frequency than areas of low detail, e.g., smooth portions of the surface, in this way, the amount of memory used to store the shape of the object is minimized, while the spatial details are preserved at high resolutions. Typically, the 3D distance field is sampled on the vertices of a cell and stored hierarchically as an octree of cells, wherein the cells are recursively partitioned according to the level of detail.
In the same way as described previously, the value of the distance field at an arbitrary location in 3D space can be computed from the distance field samples. In this case, the distance field samples are the parameters of the distance function and the distance function is a function for reconstructing the distance field from the distance field samples, also know as a reconstruction kernel. For example, the distance field can be computed from the distance field samples at the vertices of the cell by tri-linear interpolation. However, tri-quadratic interpolation, vector distance field interpolation or other reconstruction kernels can also be used. Additionally, the reconstruction kernel provides a means for computing the gradient of the distance field at any point in space. For points that lie on or near the surface of the object, the gradient points in the same direction as the surface normal.
Rendering
In the prior art, 3D ADFs have been rendered by three classes of methods: point rendering, image-order ray casting, and object-order polygonal rendering, see U.S. Pat. No. 6,396,492 “Detail-directed hierarchical distance fields,” issued to Frisken et al. on May 28, 2002, incorporated herein by reference.
Point Rendering
Point rendering of distance fields is achieved by starting from a set of points in the 3D space of the object. The distance field and its gradient vector are computed at each point and then the points are iteratively modified by moving them along the gradient vector in the direction of the surface. Motion ceases once the points reach the surface of the object to within a specified level of accuracy.
Once an array of surface points is found they can then be rendered by a number of means. For example, very simply single pixel primitives (i.e. GL_POINT) can be rendered using the OpenGL graphics API. Alternatively, an extended primitive, sometimes called a sprite or splat, can be rendered at each location.
Point rendering has the advantage of simplicity and can be quite fast. However, it can be difficult to create images without holes. Uniform coverage of the surface with points is not guaranteed and considerable effort is required to identify and fill in missing regions.
Image Order Ray Casting
Image-order ray casting methods determine pixel color and brightness in an output image on an individual pixel basis. A ray is cast from each pixel in the image through the distance field. The ray is followed from cell-to-cell until the surface is found.
As an advantage, ray casting can be as accurate as the 3D ADF, e.g., 1 part in 106 or greater. The process of identifying surface cells in the octree that contain the surface along the direction of the cast ray is fairly simple, but can be very inefficient in terms of computer memory accesses. The data associated with spatially adjacent cells in the octree are often widely separated in computer memory, resulting in a high rate of CPU memory cache misses, which degrades the overall performance of the rendering method.
When the data required for casting rays through a cell are not in the CPU cache as needed, the rendering update rate is severely decreased, sometimes to the point that interactive rendering while manipulating the model at real-time rates, e.g., ten updates per second, is impossible.
Object Order Polygonal Rendering
Object order polygonal rendering of the 3D ADF requires a polygonal representation of the ADF. Various methods for generating the polygon model from the ADF are known, including marching cubes and surface nets.
In general, object-order rendering determines the set of pixels in the image affected by each a polygon independent from any other polygon. It is common to use a z-buffer to properly combine these independent contributions, although other means are known, e.g. the painters algorithm or priority fill, wherein polygons are first sorted in a depth order prior to rendering.
Because polygon models dominate computer graphics, a large variety of polygon rendering hardware and software is available, e.g., Microsoft Direct3D and Silicon Graphic OpenGL. After the polygonal model is generated, it can be rendered to an image at a rate that is generally much higher than is possible for image-order ray casting.
However, the polygon representation uses flat primitives, and is only an approximation of the ADF. This results in images that are more faceted in appearance, and therefore cannot accurately represent curved surfaces. This is a particular problem when the rendering must be highly accurate, e.g., accurate to one part in a 106. With polygon rendering, it may be necessary to employ an unmanageably large number of very small polygons to produce surface images that are very smooth resulting in extreme memory and/or processing requirements.
Cracks in Rendered Images
In spatial partitioning methods, such as ADFs, adjacent cells can have different sizes depending on the local level of detail. As a result, the surface reconstructed from the distance field samples of one cell may not exactly match the surface reconstructed from the distance field samples of an adjacent cell resulting in the appearance of cracks in the rendered image.
It is desired to provide a method for rendering the surface represented by the 3D distance field that has the accuracy of ray casting, and the speed of polygon rendering. Additionally, it is desired that this method for rendering produces images without any crack artifacts.
It is also desired to provide a simulation that can be incorporated into manufacturing operations such as performed by milling and other machine tools. Such a simulation would enable the operator to visually identify mistakes in the machining process before the part is actually machined, thereby saving time and possibly materials.